Equalising structures with maximum likelihood detection (MLD) are typically (but not exclusively) used in communication systems in which two or more independent symbols are transmitted in parallel from one or more transmitters within the same time slot and the same frequency band. In such cases, the symbols interfere with each other. Although such interference is generally not desirable in communication systems, it is in some systems used to increase the data rate, the spectral efficiency and/or the system throughput. Examples of such systems are so-called multiple-input, multiple-output (MIMO) systems, code division multiple access (CDMA) systems and orthogonal frequency division multiplexing-code division multiple access (OFDM-CDMA) systems.
Generally, a MIMO system has nT transmitting antennas (each transmitting a different data symbol) and nR receiving antennas. Such a system has a maximum achievable data rate, which is nT time greater than an equivalent non-MIMO system. For example, in a MIMO system which has two transmitting antennas (nT=2) and two receiver antennas (nR=2), the maximum achievable data rate is two times higher than in a non-MIMO system. FIG. 1 shows the schematic block diagram of such a MIMO system for transmitting two independent symbols in parallel.
The example MIMO system shown in FIG. 1 comprises a receiver 1 and a transmitter 20 for wireless communication on the basis of orthogonal frequency division multiplexing (OFDM). The receiver 1 comprises a radio frequency (RF) part 2 and a base band part 3. The radio frequency part 2 has two antennas 4 and 5, each being connected to a low noise amplifier/downconversion unit 6 and 7, respectively. It is to be noted, that the receiver 1 can e.g. be part of a pure receiving device, or can be part of a receiving and transmitting device. In the later case, the antennas 4 and 5 are receiving as well as transmitting antennas. The downconverted signals from the units 6 and 7 are respectively forwarded and processed by a fast fourier transformation unit (FFT) 8 and 9, respectively. The transformed signals from the fourier transformation units 8 and 9 are forwarded to an equalising structure 10 and a channel estimator 11. The channel estimator 11 performs, based on the receive signal (burst) including training sequences (preamble section), the channel estimation, wherein the channel estimator 10 uses the training sequence (or reference pilots) to derive the channel estimate. Signals from the channel estimator 11 are supplied to the equalising structure 10. The equalising structure 10 performs a maximum likelihood detection in order to determine a constellation point of the signal constellation of the modulation scheme with a minimum Euclidean distance to a received signal vector as a most likely received signal vector. The specific processing is explained further below. After the equalising processing, the signals are further respectively processed in a demodulator/channel decoder 12 and 13, respectively. The output signals from the demodulator/channel decoders 12 and 13, respectively, are forwarded to a parallel/serial processing unit 14, which outputs the received data bit stream.
The example OFDM transmitter 20 schematically shown in FIG. 1 comprises a radio frequency part 21 and a base band part 22. In the base band part 22, transmit data are split into two parallel data bit streams by a serial/parallel converter 23. The two parallel data bit streams output from the converter 23 are respectively supplied to a channel coder/modulator 24 and 25, respectively. The coded and modulated signals are supplied to an inverse fast fourier transformation (IFFT) unit 26 and 27, respectively, which supply the transform signals to a respective digital/analogue-converter (DAC) and filter unit 28 and 29, respectively. The analogue filtered signals are then forwarded to a respective upconversion/power amplifying unit 30 and 31, respectively, which transmit the amplified signals via a respective transmit antenna 32 and 33, respectively. It is to be noted, that the transmitter 20 can be part of a transmitting and receiving device and the antennas 32 and 33 can be receiving as well as transmitting antennas.
As indicated by the dotted line in FIG. 1, the signals transmitted in parallel interfere with each other. For general MIMO systems the received signal column vector for each symbol is given by x having nR rows, wherein each row of the vector represents the received signal for each of the receiver antennas. The received signal x is given by,x=Hs+n  (1)where s is the column vector (nT×1) of the sent signal, H is the channel matrix (nR×nT), representing the channel response from each of the transmitter antennas to the receiving antennas and n is the noise vector (nR×1).
For the case of OFDM systems (an example of which is shown in FIG. 1), we shall denote the number of sub-carriers as M. We shall refer to the received baseband signal at sub-carrier m (m=1, . . . , M) as the received column vector xm(nR×1). Each row element of the vector is the signal from the FFT output corresponding to the mth sub-carrier for each receiver output at the receiver. The receiver vector xm can therefore be expressed as,xm=Hmsm+nm  (2)where sm is sent signal vector (nT×1), Hm is the channel matrix (nR×nT), and nm is the noise vector (nR×1). Each row element of the sent signal vector sm corresponds to the input signal of the IFFT corresponding to the mth sub-carrier for each transmitter. The elements of the channel matrix Hm correspond to the different channel responses from the elements of the transmitted vector to the elements of the received vector. It is therefore the combination of the IFFT, the multi-path channel and the FFT. It accounts for the combined effect of the IFFT, the multi-path channel and the FFT. It is well known, that for OFDM systems that such a combination leads to a channel matrix Hm whose elements hm,ij(i=1 . . . nR, j=1 . . . nT) are single complex values. For the example shown in FIG. 1 with two transmitting antennas 32, 33 and two receiving antennas 4, 5, the received signal for carrier in can be written as,
                              x          m                =                              [                                                                                x                                          m                      ,                      1                                                                                                                                        x                                          m                      ,                      2                                                                                            ]                    =                                                    [                                                                                                    h                                                  m                          ,                          11                                                                                                                                    h                                                  m                          ,                          12                                                                                                                                                                        h                                                  m                          ,                          21                                                                                                                                    h                                                  m                          ,                          22                                                                                                                    ]                            ⁡                              [                                                                                                    s                                                  m                          ,                          1                                                                                                                                                                        s                                                  m                          ,                          2                                                                                                                    ]                                      +                          [                                                                                          n                                              m                        ,                        1                                                                                                                                                        n                                              m                        ,                        2                                                                                                        ]                                                          (        3        )            
For each sub-carrier m, the normal state-of-the-art maximum likelihood detector searches over the whole set of possible transmit signals smεA (where A is the set of all possible transmit vectors) to decide in favour of the transmit signal vector ŝm which has the minimum Euclidean distance to the receive vector xm,
                                          s            ^                    m                =                  arg          ⁢                                          ⁢                                    min                                                s                  m                                ∈                A                                      ⁢                                                                                                x                    m                                    -                                                            H                      m                                        ⁢                                          s                      m                                                                                                  2                                                          (        4        )            
The size of the possible transmit signal set A, containing all of the possible sent signal vectors depends upon the number of possible sent symbols from each antenna (which depends upon the modulation constellation size) and the number of transmit antennas nT. The number of possible sent signals vectors is given by,NSV=Number of possible sent signal vectors=(Modulation Constellation Size)nT  (5)
Therefore for higher-level modulation schemes with more than two antennas, the set size can be extremely large and the number of comparisons needed to be performed for each sub-carrier in equation (4) is given byNumber of comparisons=NSV−1=(Modulation Constellation Size)nT−1  (6)
To summarise, table 1 shows the number of comparisons that have to be made in equation (4) for each sub-carrier for the commonly used modulation schemes BPSK, QPSK, 16 QAM and 64 QAM.
TABLE 1Number of comparisons for each sub-carrierfor the MLD algorithmModulationAntennas (nT, nR)Scheme2, 23, 34, 4BPSK3715QPSK156325516QAM25540956553564QAM40952621431.7 × 107
Before the comparisons for each sub-carrier in equation (4) can be performed, the vector products Hmsm have to be formed for each of the possible sent signals sm(smεA). Since the elements of Hm(hm,ij(i=1 . . . nR, j=1 . . . nT)) cannot be known perfectly at the receiver, they have to be estimated and this is traditionally achieved using a pilot tones. The elements of Hm at the receiver are therefore denoted by ĥm,ji(i=1 . . . nR, j=1 . . . nT). The vector Hmsm is a (nR×1) vector and is therefore given by,
                                          H            m                    ⁢                      s            m                          =                                            [                                                                                                                  h                        ^                                                                    m                        ,                        11                                                                                                  …                                                        …                                                                                                      h                        ^                                                                    m                        ,                                                  1                          ⁢                                                      n                            T                                                                                                                                                                                    …                                                        …                                                        …                                                        …                                                                                        …                                                        …                                                        …                                                        …                                                                                                                                      h                        ^                                                                    m                        ,                                                                              n                            R                                                    ⁢                          1                                                                                                                          …                                                        …                                                                                                      h                        ^                                                                    m                        ,                                                                              n                            R                                                    ⁢                                                      n                            T                                                                                                                                                          ]                        ·                          [                                                                                          s                                              m                        ,                        1                                                                                                                                  …                                                                                        …                                                                                                              s                                              m                        ,                                                  n                          T                                                                                                                                ]                                =                      [                                                                                Hs                                          m                      ,                      1                                                                                                                    …                                                                              …                                                                                                  Hs                                          m                      ,                                              n                        T                                                                                                                  ]                                              (        7        )            
Since Hm is a (nR×nT) matrix containing complex values and sm is a (nT×1) vector containing complex values, the total number of real multiplications and real additions to form Hmsm for all sent signal vectors is given as follows:Total real multiplications=4×nR×nT×(Modulations Constellation Size)nT  (8)Total real additions=nR×((4×nT)−2)×(Modulation Constellation Size)nT  (9)
To summarise, there are therefore two high complexity parts of the MLD algorithm (as described by equation (4)), which have to be performed for each received sub-carrier of a multi-carrier system. These are summarised as follows:    Part one: The large number of multiplications and additions of equation (7) (see equations (8) and (9), which are needed to generate the Hmsm products).    Part two: The large number of comparisons, which are required (see equation (6)).
Both these high complexity parts need to be performed M times, where M corresponds to the total number of sub-carriers. As can be seen from the above, the complexity of the prior art maximum likelihood detection schemes used in equalising structures for receiving devices in wireless communication systems is very high. Therefore, the prior art proposes several ways of reducing the complexity for maximum likelihood detection processing for multiple-input, multiple-output type systems:
Xiaodong, Li, H. C. Huang, A. Lozano, G. J. Foschini, “Reduced Complexity Detection Algorithms for Systems Using Multi-Element Arrays”, Global Telecommunications Conference (Globecom 2000), San Francisco, USA, 27-Nov.-1 December, pp. 1072-1076. This paper proposes two types of algorithms. The first algorithm uses Adaptive Group Detection (AGD), which places the possible transmitted signals from the different transmitter antennas into groups. The interference between the groups is then suppressed using interference cancellation or projection techniques. MLD detection is then performed within each group. Since MLD is only performed on a sub-set of the total transmitter antennas, the complexity is reduced. The second algorithm called Multi-step Reduced Constellation Detection performs the processing in a number of steps. The first step uses zero forcing techniques (alternatively MMSE or matched filtering can be used) and provides the second step with a coarse estimate of the sent constellation points from the different transmitter antennas. The second step then uses MLD on neighbours of the coarse estimate obtained from the zero forcing stage. Since MLD is only performed in the second stage using the nearest neighbours of the coarse estimation as candidates complexity is reduced.
G. Awater, A. van Zelst, Richard van Nee, “Reduced Complexity Space Division Multiplexing Receivers”, IEEE Vehicular Technology Conference (Spring VTC' 2000), Tokyo, Japan, 15-18 May 2000 Vol. 1. pp. 11-15. This paper describes three different algorithms for reducing the complexity of Maximum Likelihood Detection (MLD). The first algorithm uses a 2-D tree approach to represent the mathematical metrics (from the MLD equation) for the different possible sent sequences. Subsequent lower branches of the tree include the signals from an increasing number of transmit antennas. Maximum Likelihood Sequence Estimation (MLSE) techniques such as Fano's algorithm, stack decoding or retain “k-best” path are then used to decide on the best sent sequence. The second algorithm considers the different metrics in N-dimensional space and uses a survivor algorithm to select the best sent sequence. The third algorithm uses QR decomposition to reduce the N-dimension space and then uses a survivor algorithm.
J Li, K. B. Letaief, et al, “Multi-stage Low Complexity Maximum Likelihood Detection for OFDM/SDMA Wireless LANs”, IEEE International Conference on Communications (ICC#2001), Helsinki, Finland, 11-14 Feb. 2001, Vol. 4, pp. 1152-1156. The algorithm described in this paper is a 2-stage algorithm. The first stage of the algorithm uses a conventional detection method like Minimum Mean Square Error (MMSE) or Interference cancellation (IC). From this stage, “sensitive bits” (where “sensitive bits” as bits which are likely to be in error) are identified and passed to the second stage. The second stage of the algorithm uses Maximum Likelihood Detection (MLD). Since MLD for this algorithm only operates on the sensitive bits (which are sub-set of the total bits) complexity is reduced.
Jacky Ho-Yin Fan et al, “A Sub optimum MLD Detection scheme for Wireless MIMO Systems”, IEEE International Symposium on Advances in Wireless Communications (ISWC) 2002, Victoria, Canada. The algorithm discussed in this paper is similar to the algorithm discussed in (3). The algorithm consists of two stages. The first stage performs a conventional detection scheme like, Zero Forcing (ZF) or V-BLAST. If the error probability of the symbols (or vectors of symbols) from the first stage, are above a certain threshold, they are then passed to the section stage in which MLD is performed. Since only a subset of the symbols, are passed to the second stage, the complexity is reduced.
As described above, before the comparisons for each sub-carrier in equation (4) can be performed, the vector products Hmsm have to be formed for each of the possible sent signals sm (smεA). Traditionally for state of the art equalisers, all of the Hmsm products would be calculated once all of the channel estimates ĥm,ji(i=1 . . . nR, j=1 . . . nT) have been obtained. Since data information symbols are traditionally transmitted shortly after the pilot tones, the state of art equaliser has a very short period of time to calculate all of the Hmsm products and therefore the corresponding peak processing requirements are very high.